package com.nine.algorithm.recursion.fibonacci;

import java.util.Arrays;

/**
 * @author nine
 * @version 1.0
 * @description 斐波那契第n项
 * @date 24/4/30 23:40
 */
public class Fibonacci {

	/**
	 * 使用 Memoization（记忆法，也称备忘录）改进
	 *
	 * @param n
	 * @return
	 */
	public static int fibonacci(int n) {
		int[] cache = new int[n + 1];
		Arrays.fill(cache, -1);

		cache[0] = 0;
		cache[1] = 1;
		return f2(n, cache);
	}


	public static int f2(int n, int[] cache) {
		if (cache[n] != -1) {
			return cache[n];
		}

		int x = f2(n - 1, cache);
		int y = f2(n - 2, cache);
		cache[n] = x + y;
		return cache[n];
	}

	public static int f(int n) {
		if (n == 0 || n == 1) {
			return n;
		}

		int x = f(n - 1);
		int y = f(n - 2);
		return x + y;
	}

	public static void main(String[] args) {
		// 0 1 1 2 3 5 8 13 21 34 55
		int f = f(8);
		System.out.println("f = " + f);
	}

}
